/* 

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
// 递归
var pathSum = function (root, sum) {
    var res = [];
    let dfs = function (node, total, path) {
        total += node.val;
        path.push(node.val)
        if (node.left || node.right) {
            node.left && dfs(node.left, total, path.slice())
            node.right && dfs(node.right, total, path.slice())
        } else if (total === sum) {
            res.push(path)
        }
    }
    return root && dfs(root, 0, []) || res
};

// 递归
var pathSum = function (root, targetSum) {
    let res = [];

    let dfs = function (root, rest, path) {
        if (root === null) return;

        if (root.left === null && root.right === null) {
            if (root.val === rest) {
                path.push(root.val);
                res.push(path);
            }
            return;
        }

        path.push(root.val)

        dfs(root.left, rest - root.val, path.slice())
        dfs(root.right, rest - root.val, path.slice())
    }

    dfs(root, targetSum, []);

    return res;
};